/*
    统计数字在排序数组中出现的次数
 */

/* 二分查找 获取第一个元素的位置 */
function binarySearchFirst(arr, target) {
    const length = arr.length;

    let left = 0,
        right = length - 1;

    console.log(left, right);

    while (left < right) {
        let mid = (left + right) >> 1;
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
        console.log(left, right);
    }

    return left;
}

/* 二分查找 获取最后一个元素的位置 */
function binarySearchLast(arr, target) {
    const length = arr.length;

    let left = 0,
        right = length - 1;

    console.log(left, right);

    while (left < right) {
        let mid = ((left + right) >> 1) + 1;
        if (arr[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
        console.log(left, right);
    }

    return left;
}

function getFirst(arr, target, left, right) {
    if (left > right)
        return -1;

    const mid = (left + right) >> 1;

    if (arr[mid] == target) {
        if ((mid > 0 && arr[mid - 1] != target) || mid == 0) {
            return mid;
        }
        else {
            right--;
        }
    }
    else if (arr[mid] > target) {
        right = mid - 1;
    }
    else {
        left = mid + 1;
    }

    return getFirst(arr, target, left, right);
}

function getLast(arr, target, left, right) {
    if (left > right)
        return -1;

    const mid = (left + right) >> 1;

    if (arr[mid] == target) {
        if ((mid < arr.length - 1 && arr[mid + 1] != target) || mid == arr.length - 1) {
            return mid;
        }
        else {
            left++;
        }
    }
    else if (arr[mid] > target) {
        right = mid - 1;
    }
    else {
        left = mid + 1;
    }

    return getLast(arr, target, left, right);
}

function getNumberOfTarget(arr, target) {
    if (arr.length <= 0)
        return 0;

    const first = getFirst(arr, target, 0, arr.length - 1);
    const last = getLast(arr, target, 0, arr.length - 1);

    return (first != -1 && last != -1) ? (last - first + 1) : 0;
}

/* test */
let arr = [1, 2, 2, 3, 3, 3, 4, 5, 6];
console.log(getNumberOfTarget(arr, 7));
